// topK数组 array:一个对象数组 {key:xxx,num: int} ，len: 堆长度 int
export default function getTopK(array,len){
  let heap = [];
  for (let i =0;i<array.length&&i<len;i++){
    heap.push(array[i]);
  }
  if(array.length<=len){
    heap.sort((a,b)=>{
      return b["num"]-a["num"];
    })
    return heap;
  }else{
    buildHeap(heap,len)
    for (let i = len;i<array.length;i++){
      if(array[i]["num"]>heap[0]["num"]){
        heap[0] = array[i];
        minHeap(heap,0,len)
      }
    }
    heap.sort((a,b)=>{
      return b["num"]-a["num"];
    })
    return heap;
  }
}
// heap: 堆数组  heapSize: 堆的大小
function buildHeap(heap,heapSize){
  for (let i = heapSize/2;i>=0;i--){
    minHeap(heap,i,heapSize)
  }
}
//父子之间的递归调整 堆基本算法
function minHeap(heap,i,heapSize){
  let left = 2*i+1,right= 2*i+2,smallest = i;
  if(left<heapSize&&heap[left]<heap[smallest]){
    smallest = left;
  }
  if(right<heapSize&&heap[right]<heap[smallest]){
    smallest = right;
  }
  if(smallest!=i){
    let temp = heap[i];
    heap[i] = heap[smallest]
    heap[smallest] = temp;
    minHeap(heap,smallest,heapSize)
  }
}
